Das RSA-Verfahren

Das RSA-Verfahren ist ein modernes asymmetrisches kryptografisches Verfahren.
Es basiert auf einem Schlüsselpaar aus einem öffentlichen Schlüssel zum Verschlüsseln und einem privaten Schlüssel zum Entschlüsseln.

Die Lösungen der nachfolgenden Aufgaben sind in diese Textdatei zu kopieren.

Bob möchte an Alice eine geheime Nachricht senden.” Link

1. Der Empfänger einer Nachricht arbeitet nach folgender Anleitung, um einen möglichen Absender einer Nachricht seinen öffentlichen Schlüssel bekanntgeben zu können:
Schrittfolge:

a.Wähle zwei Primzahlen p und q.
Primzahltest 1
Primzahltest 2
Primzahltest 3
b.Berechne n = p*q und m=(p-1)*(q-1).

c.Bestimme eine zu  m  teilerfremde Zahl  a. 
a und e teilerfremd? Suche zu m eine teilerfremde Zahl a Lösung der Teilerfremdheit mit Funktionen Liste der zu m teilerfremden Zahlen
d.       Bilde aus diesen Zahlen den öffentlichen Schlüssel (a,n) des Empfängers.  Programmablaufplan öffentlicher Schlüssel

2.Der Absender einer zu verschlüsselnden Nachricht arbeitet nach folgender Anleitung.

a.Er wandelt seine Textnachricht zeichenweise / blockweise in Zahlen um.
Dazu nutzt er eine festzulegende Vorschrift:
- Gegebene Reihenfolge der Buchstaben im Alphabet   Aufgabe
- den ASCII-Code   Aufgabe
- oder eine beliebig andere eineindeutige Zuordnung von Zeichen zu Zahlen.  Aufgabe

b.       verschlüsselt diese Zahlen m zeichenweise / blockweise mittels
der Formel   c = ma mod n.  Beachte: m muss kleiner als n sein!
c.       Die verschlüsselten Zahlen überträgt er als Geheimtext an den Empfänger der Nachricht.

3.       Der Empfänger der Nachricht berechnet aus seinen beiden Zahlen e und phi eine neue Zahl d,  die  Inverse von e modulo phi. Programmablaufplan privater Schlüssel
          Diese muss die Bedingung    e•d mod phi = 1  erfüllen.
          Das heißt, wenn man e•d -1 durch phi teilt, dann ist der Rest 0.

a.       Probiere solange, bis das Inverse e modulo phi bestimmt ist
          
b.       Bestimmen mittels des Erweiterten Euklidischen Algorithmus
          - Erweiterter Euklidischer Algorithmus  youtube

c.        oder durch eine einfache Pythonberechnung ,  Teillösung

4.       Der Empfänger entschlüsselt mittels x = yb mod n die übermittelten Zahlen und ermittelt daraus die Zeichen des Klartextes.
          Verschlüsseln und Entschlüsseln mit Hilfe einer einfachen Pythonberechnung über die Einwegfunktionen



Wie verschlüsselt man nun ganze Texte?

Der Klartext muss zunächst in Zahlen umgewandelt und dann verschlüsselt werden.

1. Beispiel:   ASCII-Code – zeichenweise mit  a=7 und n=77    Klartext zeichenweise in ASCII-Zahlencodes und verschlüsseln

Klartext:

 I  N  F  O  R  M  A  T  I  K

Zahlencodes:

73 78 70 71 82 77 65 84 73 75

Geheimcodes:

17  1 49 51 47  0 65 28 17 26

Dieses Beispiel ist wegen x>n nicht zum Entschlüsseln geeignet. Der Text muss in kleinere Blöcke zerlegt werden.

2. Beispiel: ASCII-Code – blockweise  (Python-Programm)

(Blockgröße 3 Zeichen, 100 verschiedene Zeichen im Bereich von 0 bis 0+99)
 I   N   F  O  R  M  A  T   I   K   (X)   (X)
73 78 70 79 82 77 65 84 73 75   88    88

INF     73 78 70  : 73*10 000 + 78*100 + 70 = 737870
ORM   79 82 77 : 79*10 000 + 82*100 + 77 = 798277
ATI      65 84 73 : 65*10 000 + 84*100 + 73 = 658473
KXX    75 88 88 : 75*10 000 + 88*100 + 88 = 758888
 
Zerlegen eines Blockes in seine Bestandteile:

737870  mod 100 = 70   : 737870 // 100 = 7378
    7378  mod 100 = 78   :   7378 // 100 = 73
        73  mod 100 = 73   :     73 // 100 = 0

3. Beispiel: ASCII-Code – blockweise  Klartext blockweise in Zahlencodes ohne Verschlüsseln
     Blockgröße 3 Zeichen, 128 verschiedene Zeichen im ASCII-Code-Bereich von 0 bis 127)

Klartext:

Martin_Rinckart

Block:

  Mar      tin      _Ri      nck      art

Zahlencode:

1274098  1914094  1567081  1815019  1603956

   Mar: 77*1282 + 97 *128 + 114 = 1274098
   tin:    
    ….

Zerlegen eines Blockes in seine Bestandteile:

1274098 mod 128 = 114  :    1274098 // 128 = 9953
      9953 mod 128 =  97  :       9953 // 128 =   77
          77 mod 128 =  77  :         77 // 128 =    0
     ….